{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximal Score After Applying K Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxKelements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行 K 次操作后的最大分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。你的 <strong>起始分数</strong> 为 <code>0</code> 。</p>\n",
    "\n",
    "<p>在一步 <strong>操作</strong> 中：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选出一个满足 <code>0 &lt;= i &lt; nums.length</code> 的下标 <code>i</code> ，</li>\n",
    "\t<li>将你的 <strong>分数</strong> 增加 <code>nums[i]</code> ，并且</li>\n",
    "\t<li>将 <code>nums[i]</code> 替换为 <code>ceil(nums[i] / 3)</code> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回在 <strong>恰好</strong> 执行 <code>k</code> 次操作后，你可能获得的最大分数。</p>\n",
    "\n",
    "<p>向上取整函数 <code>ceil(val)</code> 的结果是大于或等于 <code>val</code> 的最小整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,10,10,10,10], k = 5\n",
    "<strong>输出：</strong>50\n",
    "<strong>解释：</strong>对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,10,3,3,3], k = 3\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>可以执行下述操作：\n",
    "第 1 步操作：选中 i = 1 ，nums 变为 [1,<em><strong>4</strong></em>,3,3,3] 。分数增加 10 。\n",
    "第 2 步操作：选中 i = 1 ，nums 变为 [1,<em><strong>2</strong></em>,3,3,3] 。分数增加 4 。\n",
    "第 3 步操作：选中 i = 2 ，nums 变为 [1,2,<em><strong>1</strong></em>,3,3] 。分数增加 3 。\n",
    "最后分数是 10 + 4 + 3 = 17 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximal-score-after-applying-k-operations](https://leetcode.cn/problems/maximal-score-after-applying-k-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximal-score-after-applying-k-operations](https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,10,10,10,10]\\n5', '[1,10,3,3,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        Bheap=[]\n",
    "        ans=0\n",
    "        while nums:\n",
    "            heapq.heappush(Bheap,-nums.pop())\n",
    "        while k:\n",
    "            k-=1\n",
    "            temp=-heapq.heappop(Bheap)\n",
    "            ans+=temp\n",
    "            heapq.heappush(Bheap,-((temp+2)//3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        def func(x):\n",
    "            return ceil(x/3)\n",
    "        helplist=[[] for _ in range(20)]\n",
    "        for i in nums:\n",
    "            tmp=ceil(math.log(i,3))\n",
    "            helplist[tmp].append(i)\n",
    "        j=19\n",
    "        res=0\n",
    "        while k:\n",
    "            if helplist[j]:\n",
    "                if k>=len(helplist[j]):\n",
    "                    k-=len(helplist[j])\n",
    "                    res+=sum(helplist[j])\n",
    "                    helplist[j-1].extend(map(func,helplist[j]))\n",
    "                else:\n",
    "                    return res+sum(sorted(helplist[j])[-k:])\n",
    "            if j!=0:j-=1\n",
    "            else:return res+k\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        sorted_list = SortedList(nums)\n",
    "        rs = 0\n",
    "        for _ in range(k):\n",
    "            max_num = sorted_list.pop()\n",
    "            rs += max_num\n",
    "            sorted_list.add(ceil(max_num / 3))\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "import sortedcontainers\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums, k: int):\n",
    "\n",
    "        sortnums = sortedcontainers.SortedList(nums)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            s = sortnums.pop()\n",
    "            ans += s\n",
    "            sortnums.add(math.ceil(s/3))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        arr = SortedList(nums)\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            val = arr.pop()\n",
    "            res += val\n",
    "            arr.add((val+2)//3)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        tmp = SortedList(nums)\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            t = tmp[-1]\n",
    "            res+=t\n",
    "            tmp.remove(t)\n",
    "            tmp.add(ceil(t/3))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        from math import ceil\n",
    "        sl = SortedList()\n",
    "        for num in nums:\n",
    "            sl.add(num)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            temp = sl.pop()\n",
    "            ans += temp\n",
    "            sl.add(ceil(temp/3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        dq = SortedList(nums)\n",
    "        score = 0\n",
    "        for i in range(k):\n",
    "            max_val = dq.pop(-1)\n",
    "            score+=max_val\n",
    "            dq.add( ceil(max_val/3))\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        st = SortedList()\n",
    "        res = 0\n",
    "\n",
    "        for num in nums:\n",
    "            st.add(num)\n",
    "        \n",
    "        while k > 0:\n",
    "            # print(st)\n",
    "            tmp = st.pop(-1)\n",
    "            # print(tmp)\n",
    "            res += tmp \n",
    "            st.add(ceil(tmp / 3))\n",
    "            k -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SortedList:\n",
    "    def __init__(self, iterable=[], _load=200):\n",
    "        \"\"\"Initialize sorted list instance.\"\"\"\n",
    "        values = sorted(iterable)\n",
    "        self._len = _len = len(values)\n",
    "        self._load = _load\n",
    "        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n",
    "        self._list_lens = [len(_list) for _list in _lists]\n",
    "        self._mins = [_list[0] for _list in _lists]\n",
    "        self._fen_tree = []\n",
    "        self._rebuild = True\n",
    " \n",
    "    def _fen_build(self):\n",
    "        \"\"\"Build a fenwick tree instance.\"\"\"\n",
    "        self._fen_tree[:] = self._list_lens\n",
    "        _fen_tree = self._fen_tree\n",
    "        for i in range(len(_fen_tree)):\n",
    "            if i | i + 1 < len(_fen_tree):\n",
    "                _fen_tree[i | i + 1] += _fen_tree[i]\n",
    "        self._rebuild = False\n",
    " \n",
    "    def _fen_update(self, index, value):\n",
    "        \"\"\"Update `fen_tree[index] += value`.\"\"\"\n",
    "        if not self._rebuild:\n",
    "            _fen_tree = self._fen_tree\n",
    "            while index < len(_fen_tree):\n",
    "                _fen_tree[index] += value\n",
    "                index |= index + 1\n",
    " \n",
    "    def _fen_query(self, end):\n",
    "        \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    " \n",
    "        _fen_tree = self._fen_tree\n",
    "        x = 0\n",
    "        while end:\n",
    "            x += _fen_tree[end - 1]\n",
    "            end &= end - 1\n",
    "        return x\n",
    " \n",
    "    def _fen_findkth(self, k):\n",
    "        \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"\n",
    "        _list_lens = self._list_lens\n",
    "        if k < _list_lens[0]:\n",
    "            return 0, k\n",
    "        if k >= self._len - _list_lens[-1]:\n",
    "            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    " \n",
    "        _fen_tree = self._fen_tree\n",
    "        idx = -1\n",
    "        for d in reversed(range(len(_fen_tree).bit_length())):\n",
    "            right_idx = idx + (1 << d)\n",
    "            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n",
    "                idx = right_idx\n",
    "                k -= _fen_tree[idx]\n",
    "        return idx + 1, k\n",
    " \n",
    "    def _delete(self, pos, idx):\n",
    "        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    " \n",
    "        self._len -= 1\n",
    "        self._fen_update(pos, -1)\n",
    "        del _lists[pos][idx]\n",
    "        _list_lens[pos] -= 1\n",
    " \n",
    "        if _list_lens[pos]:\n",
    "            _mins[pos] = _lists[pos][0]\n",
    "        else:\n",
    "            del _lists[pos]\n",
    "            del _list_lens[pos]\n",
    "            del _mins[pos]\n",
    "            self._rebuild = True\n",
    " \n",
    "    def _loc_left(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    " \n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    " \n",
    "        lo, pos = -1, len(_lists) - 1\n",
    "        while lo + 1 < pos:\n",
    "            mi = (lo + pos) >> 1\n",
    "            if value <= _mins[mi]:\n",
    "                pos = mi\n",
    "            else:\n",
    "                lo = mi\n",
    " \n",
    "        if pos and value <= _lists[pos - 1][-1]:\n",
    "            pos -= 1\n",
    " \n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value <= _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    " \n",
    "        return pos, idx\n",
    " \n",
    "    def _loc_right(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    " \n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    " \n",
    "        pos, hi = 0, len(_lists)\n",
    "        while pos + 1 < hi:\n",
    "            mi = (pos + hi) >> 1\n",
    "            if value < _mins[mi]:\n",
    "                hi = mi\n",
    "            else:\n",
    "                pos = mi\n",
    " \n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value < _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    " \n",
    "        return pos, idx\n",
    " \n",
    "    def add(self, value):\n",
    "        \"\"\"Add `value` to sorted list.\"\"\"\n",
    "        _load = self._load\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    " \n",
    "        self._len += 1\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            self._fen_update(pos, 1)\n",
    "            _list = _lists[pos]\n",
    "            _list.insert(idx, value)\n",
    "            _list_lens[pos] += 1\n",
    "            _mins[pos] = _list[0]\n",
    "            if _load + _load < len(_list):\n",
    "                _lists.insert(pos + 1, _list[_load:])\n",
    "                _list_lens.insert(pos + 1, len(_list) - _load)\n",
    "                _mins.insert(pos + 1, _list[_load])\n",
    "                _list_lens[pos] = _load\n",
    "                del _list[_load:]\n",
    "                self._rebuild = True\n",
    "        else:\n",
    "            _lists.append([value])\n",
    "            _mins.append(value)\n",
    "            _list_lens.append(1)\n",
    "            self._rebuild = True\n",
    " \n",
    "    def discard(self, value):\n",
    "        \"\"\"Remove `value` from sorted list if it is a member.\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            if idx and _lists[pos][idx - 1] == value:\n",
    "                self._delete(pos, idx - 1)\n",
    " \n",
    "    def remove(self, value):\n",
    "        \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"\n",
    "        _len = self._len\n",
    "        self.discard(value)\n",
    "        if _len == self._len:\n",
    "            raise ValueError('{0!r} not in list'.format(value))\n",
    " \n",
    "    def pop(self, index=-1):\n",
    "        \"\"\"Remove and return value at `index` in sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        value = self._lists[pos][idx]\n",
    "        self._delete(pos, idx)\n",
    "        return value\n",
    " \n",
    "    def bisect_left(self, value):\n",
    "        \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"\n",
    "        pos, idx = self._loc_left(value)\n",
    "        return self._fen_query(pos) + idx\n",
    " \n",
    "    def bisect_right(self, value):\n",
    "        \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"\n",
    "        pos, idx = self._loc_right(value)\n",
    "        return self._fen_query(pos) + idx\n",
    " \n",
    "    def count(self, value):\n",
    "        \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"\n",
    "        return self.bisect_right(value) - self.bisect_left(value)\n",
    " \n",
    "    def __len__(self):\n",
    "        \"\"\"Return the size of the sorted list.\"\"\"\n",
    "        return self._len\n",
    " \n",
    "    def __getitem__(self, index):\n",
    "        \"\"\"Lookup value at `index` in sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        return self._lists[pos][idx]\n",
    " \n",
    "    def __delitem__(self, index):\n",
    "        \"\"\"Remove value at `index` from sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        self._delete(pos, idx)\n",
    " \n",
    "    def __contains__(self, value):\n",
    "        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_left(value)\n",
    "            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n",
    "        return False\n",
    " \n",
    "    def __iter__(self):\n",
    "        \"\"\"Return an iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in self._lists for value in _list)\n",
    " \n",
    "    def __reversed__(self):\n",
    "        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in reversed(self._lists) for value in reversed(_list))\n",
    " \n",
    "    def __repr__(self):\n",
    "        \"\"\"Return string representation of sorted list.\"\"\"\n",
    "        return 'SortedList({0})'.format(list(self))\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums=SortedList(nums)\n",
    "        ret=0\n",
    "        while k:\n",
    "            t=nums.pop(-1)\n",
    "            ret+=t\n",
    "            nums.add(ceil(t/3))\n",
    "            k-=1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        t=k\n",
    "        res=0\n",
    "        nums.sort(reverse=True)\n",
    "        for i in nums:\n",
    "            if k>0:\n",
    "                nums.append(ceil(float(i)/3))\n",
    "                k-=1\n",
    "            if k==0:\n",
    "                break\n",
    "        nums.sort(reverse=True)\n",
    "        for i in nums:\n",
    "            if t>0:\n",
    "                res+=i\n",
    "                t-=1\n",
    "            if t==0:\n",
    "                break\n",
    "        return res\n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=-nums[i]\n",
    "        heapq.heapify(nums)\n",
    "        ans=0\n",
    "\n",
    "        for i in range(k):\n",
    "            a=-heapq.heappop(nums)\n",
    "            ans+=a\n",
    "            heapq.heappush(nums,-math.ceil(a/3))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums_len = len(nums)\n",
    "        # # print(nums_len)\n",
    "        # res = 0\n",
    "        # for i in range (k):\n",
    "        #     tmp = max(nums)\n",
    "        #     # print(\"tmp\",tmp)\n",
    "        #     res = res + tmp\n",
    "        #     for j in range (nums_len):\n",
    "        #         if nums[j] == tmp:\n",
    "        #             nums[j] = ceil(nums[j]/3)\n",
    "        #             break\n",
    "        #     # print(\"nums=\",nums)\n",
    "        #     # print(\"res=\",res) \n",
    "        res = 0\n",
    "        for i in range (nums_len):\n",
    "            nums[i] = -nums[i]\n",
    "        heapify(nums)\n",
    "        for j in range (k):\n",
    "            res = res - heapreplace(nums,nums[0]//3)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -nums[i]  # 最大堆\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -nums[i]  # 最大堆\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(map(lambda x:-x,nums))\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            p = -heappop(nums)\n",
    "            ans+=p\n",
    "            heappush(nums,-ceil(p/3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(map(lambda x: -x, nums))\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        while k > 0:\n",
    "            x = heappop(nums)\n",
    "            if x == 0:\n",
    "                break\n",
    "            ans -= x\n",
    "            heappush(nums, -((-x - 1) // 3 + 1))\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] = -nums[i]\n",
    "        heapify(nums)  # 最大堆\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] = -nums[i]\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0]//3)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=-nums[i]\n",
    "        heapify(nums)\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            a=-heappop(nums)\n",
    "            ans+=a\n",
    "            heappush(nums,-a//3)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] *= -1\n",
    "        ans = 0\n",
    "        heapq.heapify(nums)\n",
    "        while k and nums[0] < -1:\n",
    "            k -= 1\n",
    "            ans -= nums[0]\n",
    "            heapq.heapreplace(nums, -((-nums[0] + 2) // 3))\n",
    "        return ans + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        score=0\n",
    "        nums.sort(reverse=True)\n",
    "        nums_c=[0]*k\n",
    "        score+=nums[0]\n",
    "        nums_c[0]=ceil(nums[0] / 3)\n",
    "        m=1\n",
    "        n=0\n",
    "        p=1\n",
    "        for i in range(1,k):\n",
    "            if m<=len(nums)-1 and nums[m]>nums_c[n]:\n",
    "                score+=nums[m]\n",
    "                nums_c[p]=ceil(nums[m] / 3)\n",
    "                m+=1\n",
    "            else :\n",
    "                score+=nums_c[n]\n",
    "                nums_c[p]=ceil(nums_c[n] / 3)\n",
    "                n+=1\n",
    "            p=p+1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        score=0\n",
    "        nums.sort(reverse=True)\n",
    "        nums_c=[0]*k\n",
    "        score+=nums[0]\n",
    "        nums_c[0]=ceil(nums[0] / 3)\n",
    "        m=1\n",
    "        n=0\n",
    "        p=1\n",
    "        for i in range(1,k):\n",
    "            if m<=len(nums)-1 and nums[m]>nums_c[n]:\n",
    "                score+=nums[m]\n",
    "                nums_c[p]=ceil(nums[m] / 3)\n",
    "                m+=1\n",
    "            else :\n",
    "                score+=nums_c[n]\n",
    "                nums_c[p]=ceil(nums_c[n] / 3)\n",
    "                n+=1\n",
    "            p=p+1\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        n = 0\n",
    "        ans = 0\n",
    "        while n < k:\n",
    "            nums.sort()\n",
    "            ans += nums[-1]\n",
    "            c = (nums[-1]+2)//3\n",
    "            n += 1\n",
    "            z = [c]\n",
    "            m = 1\n",
    "            while n < k and m < len(nums) and nums[-m-1] >= c:\n",
    "                ans += nums[-m-1]\n",
    "                z.append((nums[-m-1]+2)//3)\n",
    "                n += 1\n",
    "                m += 1\n",
    "            while n < k:\n",
    "                nums = nums[:-m] + z[::-1]\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        n = 0\n",
    "        ans = 0\n",
    "        while n < k:\n",
    "            nums.sort()\n",
    "            ans += nums[-1]\n",
    "            c = (nums[-1]+2)//3\n",
    "            n += 1\n",
    "            z = [c]\n",
    "            m = 1\n",
    "            while n < k and m < len(nums) and nums[-m-1] >= c:\n",
    "                ans += nums[-m-1]\n",
    "                z.append((nums[-m-1]+2)//3)\n",
    "                n += 1\n",
    "                m += 1\n",
    "            while n < k:\n",
    "                nums = nums[:-m] + z[::-1]\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "    \n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        ans = 0\n",
    "        q = []\n",
    "        i = 0\n",
    "        while k > 0:\n",
    "            if i == 0:\n",
    "                ans += nums[i]\n",
    "                x = (nums[i] + 2)//3\n",
    "                i += 1\n",
    "                heappush(q, -x)\n",
    "            else:\n",
    "                max_q = - heappop(q)\n",
    "                if i < len(nums) and  nums[i] > max_q :\n",
    "                    ans += nums[i]\n",
    "                    x = (nums[i] + 2) // 3\n",
    "                    i += 1\n",
    "                    heappush(q, -x)\n",
    "                    heappush(q, - max_q)\n",
    "                else:\n",
    "                    ans += max_q\n",
    "                    x = (max_q + 2) // 3\n",
    "                    heappush(q, -x)\n",
    "            \n",
    "            k -= 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        score = 0\n",
    "        for _ in range(k):\n",
    "            current = nums.pop()\n",
    "            score += current\n",
    "            insort(nums, ceil(current / 3))\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0  # 结果\n",
    "        count = 0  # 次数\n",
    "        n = len(nums)  # 长度\n",
    "        while count < k:\n",
    "            nums = sorted(nums)  # 排序\n",
    "            i = n - 1  # 数组下标\n",
    "            min = math.ceil(nums[-1] / 3)  # 最大数使用一次后的值，如果其他数比min小重新循环排序\n",
    "            # 如果列表没遍历完，执行次数没有超过k次，且该值【大于等于】最大数使用后的值，继续循环\n",
    "            while i >= 0 and count < k and nums[i] >= min:\n",
    "                sum += nums[i]\n",
    "                i -= 1\n",
    "                count += 1\n",
    "            # 如果循环过后，次数恰好等于k次，结束循环\n",
    "            if count == k:\n",
    "                break\n",
    "            # 将使用过的数，在数组中修改成除以3的值\n",
    "            while i < n - 1:\n",
    "                i += 1  # 此处注意当前的i没有参与过计算，所以不能除以3，要先将i加1\n",
    "                nums[i] = math.ceil(nums[i] / 3)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] *= -1\n",
    "        heapify(nums)\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            v = -heappop(nums)\n",
    "            ans += v\n",
    "            heappush(nums, -((v+2)//3))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        heap=[]\n",
    "        for num in nums:\n",
    "            heapq.heappush(heap,-num)\n",
    "        \n",
    "        result=0\n",
    "        for i in range(k):\n",
    "            t=-heapq.heappop(heap)\n",
    "            result+=t\n",
    "            t=math.ceil(t/3)\n",
    "            heapq.heappush(heap,-t)\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = - nums[i]\n",
    "        heapify(nums)\n",
    "        #print(nums)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "            #print(nums)\n",
    "        return ans\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -nums[i]  # 最大堆\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -nums[i]  # 最大堆\n",
    "        heapify(nums)  # 原地堆化\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            ans -= heapreplace(nums, nums[0] // 3)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "    #     score = 0\n",
    "    #     for x in range(k):\n",
    "    #         max_value = max(nums)\n",
    "    #         index = nums.index(max_value)\n",
    "    #         nums[index] = int(max_value / 3) + 1\n",
    "    #         score += max_value\n",
    "    #     return score\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        # h = [-x for x in nums]\n",
    "        # heapify(h)\n",
    "        h = []\n",
    "        for item in nums:\n",
    "            heapq.heappush(h, -item)\n",
    "        result = 0\n",
    "        for _ in range(k):\n",
    "            top = -heappop(h)\n",
    "            result += top\n",
    "            heappush(h, -math.ceil(top/3))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        pq = [-x for x in nums]\n",
    "        heapify(pq)\n",
    "        ans = 0\n",
    "        while k > 0:\n",
    "            ans += -pq[0]\n",
    "            heapreplace(pq, -ceil(-pq[0] / 3))\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        q = [-num for num in nums]\n",
    "        heapq.heapify(q)\n",
    "        res = 0\n",
    "        while k:\n",
    "            x = heapq.heappop(q)\n",
    "            res += abs(x)\n",
    "            heapq.heappush(q, -((-x + 2) // 3))\n",
    "            k -= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# 答案 - 官方题解\n",
    "# https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/2484596/zhi-xing-k-ci-cao-zuo-hou-de-zui-da-fen-a1jub/        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        q=[]\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            heappush(q,-i)\n",
    "        for _ in range(k):\n",
    "            temp=-heappop(q)\n",
    "            ans+=temp\n",
    "            heappush(q,-(math.ceil(temp/3)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums = [-i for i in nums]\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        while k:\n",
    "            k -= 1\n",
    "            v = heappop(nums)\n",
    "            ans += -v\n",
    "            heappush(nums, -ceil(-v / 3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        # python 中的 heap 默认是小根堆，需要对元素取相反数\n",
    "        q = [-x for x in nums]\n",
    "        heapify(q)\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            x = heappop(q)\n",
    "            ans += -x\n",
    "            heappush(q, -((-x + 2) // 3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        n = 0\n",
    "        m = len(nums)\n",
    "        ans = 0\n",
    "        while n < k:\n",
    "            nums.sort()\n",
    "            c = (nums[-1]+2)//3\n",
    "            i = m - 1\n",
    "            while i >= 0 and n < k  and nums[i] >= c:\n",
    "                ans += nums[i]\n",
    "                n += 1\n",
    "                i -= 1\n",
    "            if n == k:\n",
    "                break\n",
    "            i += 1\n",
    "            while i < m:\n",
    "                nums[i] = (nums[i]+2)//3\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        q = [-x for x in nums]\n",
    "        heapify(q)\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(k):\n",
    "            x = heappop(q)\n",
    "            ans += -x\n",
    "            heappush(q, -((-x + 2) // 3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(1,len(nums)):\n",
    "            son=i\n",
    "            while son!=0:\n",
    "                father=(son-1)//2\n",
    "                if nums[father]<nums[son]:\n",
    "                    nums[father],nums[son]=nums[son],nums[father]\n",
    "                    son=father\n",
    "                else:\n",
    "                    break\n",
    "        count=0\n",
    "        \n",
    "        for i in range(k):\n",
    "            count+=nums[0]\n",
    "            nums[0]=(nums[0]+2)//3\n",
    "            father=0\n",
    "            maxnum=-1\n",
    "            while True:\n",
    "                left,right=2*father+1,2*father+2\n",
    "                son=None\n",
    "                if right<len(nums) and nums[right]>maxnum:\n",
    "                    maxnum,son=nums[right],right\n",
    "                if left<len(nums) and nums[left]>maxnum:\n",
    "                    maxnum,son=nums[left],left\n",
    "                if son!=None:\n",
    "                    nums[father],nums[son]=nums[son],nums[father]\n",
    "                    father=son\n",
    "                    maxnum=nums[father]\n",
    "                else:\n",
    "                    break\n",
    "        return count\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        max_num = nums[l-1] / 3 if nums[l-1] % 3 == 0 else int(nums[l-1] / 3) + 1\n",
    "        while k:\n",
    "            if nums[l-1] > max_num:\n",
    "                res += nums[l-1]\n",
    "                nums[l-1] = nums[l-1] / 3 if nums[l-1] % 3 == 0 else int(nums[l-1] / 3) + 1\n",
    "                l -= 1\n",
    "                k -= 1\n",
    "            else:\n",
    "                nums.sort()\n",
    "                l = len(nums)\n",
    "                max_num = nums[l - 1] / 3 if nums[l - 1] % 3 == 0 else int(nums[l - 1] / 3) + 1\n",
    "                if nums[l-1] == 1:\n",
    "                    res += k\n",
    "                    break\n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] *= -1\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            ans -= heapreplace(nums,nums[0]//3)\n",
    "        return ans\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "    # 堆练习\n",
    "        import heapq\n",
    "        score = 0\n",
    "        heapq._heapify_max(nums)\n",
    "        for i in range(k):\n",
    "            temp = nums[0]\n",
    "            score += temp\n",
    "            heapq._heapreplace_max(nums,math.ceil(temp/3))\n",
    "        return score\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        q = PriorityQueue(len(nums))\n",
    "        [q.put(-i) for i in nums]\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            t_v = -q.get()\n",
    "            res += t_v\n",
    "            q.put(-1*ceil( t_v / 3 ))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class PriorityQueue:\n",
    "        def __init__(self, nums: List[int]):\n",
    "            self.pq = nums\n",
    "            self.pq.sort(reverse=True)\n",
    "\n",
    "        def top(self):\n",
    "            self.pq[0], self.pq[-1] = self.pq[-1], self.pq[0]\n",
    "            t = self.pq.pop()\n",
    "            id = 0\n",
    "            while id < (len(self.pq)-1)/2:\n",
    "                sid = 2 * id + 1\n",
    "                if len(self.pq) > sid+1 and self.pq[sid+1] > self.pq[sid]:\n",
    "                    sid += 1\n",
    "                if self.pq[id] > self.pq[sid]:\n",
    "                    break\n",
    "                self.pq[id], self.pq[sid] = self.pq[sid], self.pq[id]\n",
    "                id = sid\n",
    "            return t\n",
    "        \n",
    "        def push(self, val):\n",
    "            self.pq.append(val)\n",
    "            id = len(self.pq) - 1\n",
    "            while id>0 and self.pq[(id-1)//2] < val:\n",
    "                self.pq[(id-1)//2], self.pq[id] = self.pq[id], self.pq[(id-1)//2]\n",
    "                id = (id-1)//2\n",
    "\n",
    "\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        qn = self.PriorityQueue(nums)\n",
    "        score = 0\n",
    "        for _ in range(k):\n",
    "            t = qn.top()\n",
    "            print(t)\n",
    "            score += t\n",
    "            qn.push((t+2)//3)\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        result = 0\n",
    "        tmp = 0\n",
    "        lens = len(nums)\n",
    "\n",
    "        nums.sort(reverse=True)\n",
    "        print(nums)\n",
    "\n",
    "        for i in range(k):\n",
    "            if nums[tmp] >= nums[0]:\n",
    "                result += nums[tmp]\n",
    "                nums[tmp] = ceil(nums[tmp]/3)\n",
    "                if tmp+1 < lens:\n",
    "                    tmp += 1\n",
    "                else: \n",
    "                    tmp = 0\n",
    "                # print(result)\n",
    "            else:\n",
    "                nums.sort(reverse=True)\n",
    "                result += nums[0]\n",
    "                nums[0] = ceil(nums[0]/3)\n",
    "                tmp = 1\n",
    "                # print(result)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=2530 lang=python3\n",
    "#\n",
    "# [2530] 执行 K 次操作后的最大分数\n",
    "#\n",
    "# https://leetcode.cn/problems/maximal-score-after-applying-k-operations/description/\n",
    "#\n",
    "# algorithms\n",
    "# Medium (45.33%)\n",
    "# Likes:    40\n",
    "# Dislikes: 0\n",
    "# Total Accepted:    14.5K\n",
    "# Total Submissions: 27.2K\n",
    "# Testcase Example:  '[10,10,10,10,10]\\n5'\n",
    "#\n",
    "# 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。\n",
    "#\n",
    "# 在一步 操作 中：\n",
    "#\n",
    "#\n",
    "# 选出一个满足 0 <= i < nums.length 的下标 i ，\n",
    "# 将你的 分数 增加 nums[i] ，并且\n",
    "# 将 nums[i] 替换为 ceil(nums[i] / 3) 。\n",
    "#\n",
    "#\n",
    "# 返回在 恰好 执行 k 次操作后，你可能获得的最大分数。\n",
    "#\n",
    "# 向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。\n",
    "#\n",
    "#\n",
    "#\n",
    "# 示例 1：\n",
    "#\n",
    "#\n",
    "# 输入：nums = [10,10,10,10,10], k = 5\n",
    "# 输出：50\n",
    "# 解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。\n",
    "#\n",
    "#\n",
    "# 示例 2：\n",
    "#\n",
    "#\n",
    "# 输入：nums = [1,10,3,3,3], k = 3\n",
    "# 输出：17\n",
    "# 解释：可以执行下述操作：\n",
    "# 第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。\n",
    "# 第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。\n",
    "# 第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。\n",
    "# 最后分数是 10 + 4 + 3 = 17 。\n",
    "#\n",
    "#\n",
    "#\n",
    "#\n",
    "# 提示：\n",
    "#\n",
    "#\n",
    "# 1 <= nums.length, k <= 10^5\n",
    "# 1 <= nums[i] <= 10^9\n",
    "#\n",
    "#\n",
    "#\n",
    "\n",
    "import heapq\n",
    "from math import ceil\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "def _get_max(nums):\n",
    "    maxidx, maxval = -1, 0\n",
    "    for idx, num in enumerate(nums):\n",
    "        if num > maxval:\n",
    "            maxidx = idx\n",
    "            maxval = num\n",
    "    return maxidx, maxval\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        # h = [-num for num in nums]\n",
    "        # heapq.heapify(h)\n",
    "        for idx, num in enumerate(nums):\n",
    "            nums[idx] = -num\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        res = 0\n",
    "        for _ in range(k):\n",
    "            maxval = -heapq.heappop(nums)\n",
    "            res += maxval\n",
    "            heapq.heappush(nums, -((maxval + 2)//3))\n",
    "        return res\n",
    "\n",
    "    # def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "    #     d = SortedDict()\n",
    "    #     for num in nums:\n",
    "    #         d[num] = d.get(num, 0) + 1\n",
    "\n",
    "    #     res = 0\n",
    "    #     for _ in range(k):\n",
    "    #         maxval, cnt = d.peekitem()\n",
    "    #         res += maxval\n",
    "    #         if cnt == 1:\n",
    "    #             d.popitem()\n",
    "    #         else:\n",
    "    #             d[maxval] -= 1\n",
    "    #         maxval = ceil(maxval / 3)\n",
    "    #         d[maxval] = d.get(maxval, 0) + 1\n",
    "    #     return res\n",
    "\n",
    "\n",
    "    # def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "    #     res = 0\n",
    "    #     for _ in range(k):\n",
    "    #         maxidx, maxval =  _get_max(nums)\n",
    "    #         res += maxval\n",
    "    #         nums[maxidx] = ceil(maxval / 3)\n",
    "    #     return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        for i in range(k):\n",
    "            t=math.ceil(nums[i]/3)\n",
    "            nums.append(t)\n",
    "        nums.sort(reverse=True)\n",
    "        return sum(nums[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        result = 0\n",
    "        tmp = 0\n",
    "        lens = len(nums)\n",
    "\n",
    "        nums.sort(reverse=True)\n",
    "        print(nums)\n",
    "\n",
    "        for i in range(k):\n",
    "            if nums[tmp] >= nums[0]:\n",
    "                result += nums[tmp]\n",
    "                nums[tmp] = ceil(nums[tmp]/3)\n",
    "                if tmp+1 < lens:\n",
    "                    tmp += 1\n",
    "                else: \n",
    "                    tmp = 0\n",
    "                \n",
    "            else:\n",
    "                nums.sort(reverse=True)\n",
    "                result += nums[0]\n",
    "                nums[0] = ceil(nums[0]/3)\n",
    "                tmp = 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import math\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        sl = SortedList()\n",
    "        for i in nums:\n",
    "            sl.add(i)\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            res += sl[-1]\n",
    "            mm = sl[-1]\n",
    "            sl.pop(index=-1)\n",
    "            sl.add(math.ceil(mm/3))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums = [-x for x in nums]\n",
    "        heapq.heapify(nums)\n",
    "        for _ in range(k):\n",
    "            item_num = -heapq.heappop(nums)\n",
    "            res += item_num\n",
    "            print(item_num, ceil(item_num / 3))\n",
    "            heapq.heappush(nums, -ceil(item_num / 3))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        l = SortedList()\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            l.add(i)\n",
    "        for i in range(k):\n",
    "            ans = ans + l[-1]\n",
    "            l.add(int((l[-1] + 2) / 3))\n",
    "            l.discard(l[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        ans = 0\n",
    "        st = SortedList()\n",
    "        for n in nums:\n",
    "            st.add(n)\n",
    "        for i in range(k):\n",
    "            n = st.pop()\n",
    "            ans += n\n",
    "            st.add(ceil(n/3))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        S=SortedList()\n",
    "        for i in nums:\n",
    "            S.add(i)\n",
    "        res=0\n",
    "        for j in range(k):\n",
    "            temp=S[-1]\n",
    "            S.discard(temp)\n",
    "            res+=temp\n",
    "            S.add((temp+2)//3)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        s = SortedList(nums)\n",
    "        score = 0\n",
    "        i = 0\n",
    "        while i < k:\n",
    "            max_item = s.pop()\n",
    "            if max_item == 1:\n",
    "                score += k - i\n",
    "                break\n",
    "            curr = max_item\n",
    "            score += curr\n",
    "            curr = ceil(curr / 3)\n",
    "            i += 1\n",
    "            while (len(s) == 0 or curr > s[-1]) and i < k:\n",
    "                score += curr\n",
    "                curr = ceil(curr / 3)\n",
    "                i += 1\n",
    "            s.add(curr)\n",
    "        return score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        s = SortedList(nums)\n",
    "        score = 0\n",
    "        i = 0\n",
    "        while i < k:\n",
    "            max_item = s.pop()\n",
    "            if max_item == 1:\n",
    "                score += k - i\n",
    "                break\n",
    "            curr = max_item\n",
    "            score += curr\n",
    "            curr = ceil(curr / 3)\n",
    "            i += 1\n",
    "            while (len(s) == 0 or curr > s[-1]) and i < k:\n",
    "                score += curr\n",
    "                curr = ceil(curr / 3)\n",
    "                i += 1\n",
    "            s.add(curr)\n",
    "        return score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList(nums)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            x = sl.pop()\n",
    "            ans += x\n",
    "            sl.add((x + 2)//3)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        arr = SortedList()\n",
    "        for num in nums:\n",
    "            arr.add(num)\n",
    "        count = 0\n",
    "        sum = 0\n",
    "        while count < k:\n",
    "            count += 1\n",
    "            nu = arr.pop()\n",
    "            sum += nu\n",
    "            arr.add(math.ceil(nu / 3))\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def maxKelements(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        heap = SortedList(nums)\n",
    "        for _ in range(k):\n",
    "            num = heap.pop()\n",
    "            ans = ans + num\n",
    "            heap.add(ceil(num/3))\n",
    "        return ans\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
